package com.wj.datastructure;

import org.junit.Test;

/**
 * @author WangJin
 * @version 1.0
 * @date 2022/1/18 9:30
 */
public class DataStructure {

    /**
     * 定义一个数组
     */
    Integer[] arr = {5,15,4,10,7,8,11,2,13,1,6,14,9,3,12};

    /**
     * 一、选择排序
     */
    @Test
    public void SelectSort(){

        System.out.println("原始数组为：");
        print(arr);
        System.out.println("\n");

        int n = 0; //定义交换次数
        int k = 1; //定义循环次数

        long startTime = System.currentTimeMillis();    //获取开始时间

            for (int i = 0; i < arr.length-1; i++) {

                System.out.print("经过第"+ "["+ k++ +"]" + "次循环之后，数组内容！");
                System.out.println("\n");
                System.out.println("===================================选择排序=======================================");

                int posMin = i;

            for(int j = i+1; j<arr.length; j++){
//                posMin = arr[j] < arr[posMin] ? j : posMin;
                if(arr[j] < arr[posMin])
                    posMin = j;

                System.out.println("最小数位置posMin:"+posMin);

                }

                swap(arr,i,posMin);
                n++;
                System.out.print("经过第"+ n + "次交换之后，数组内容！");
                print(arr);
                System.out.println("\n");

                System.out.println("***********************************选择排序***************************************");
            }

        long endTime = System.currentTimeMillis();    //获取结束时间

        long Time = endTime - startTime;

        System.out.println("选择排序运行时间：" + Time);
    }

    /**
     * 二、冒泡排序
     */
    @Test
    public void BubbleSort() {

        System.out.println("原始数组为：");
        print(arr);
        System.out.println("\n");

        int n = 0; //定义交换次数
        int k = 1; //定义循环次数

        long startTime = System.currentTimeMillis();    //获取开始时间

        for (int j = arr.length-1; j > 0; j--) {

            System.out.print("经过第"+ "["+ k++ +"]" + "次循环之后，数组内容！");
            System.out.println("\n");
            System.out.println("===================================冒泡排序=======================================");

            for (int i = 0; i < j; i++) {
                if (arr[i] > arr[i + 1]){
                    swap(arr, i, i + 1);
                n++;
                System.out.print("经过第"+ n + "次交换之后，数组内容！");
                print(arr);
                System.out.println("\n");
                }
            }
            System.out.println("***********************************冒泡排序***************************************");
        }
        long endTime = System.currentTimeMillis();    //获取结束时间

        long Time = endTime - startTime;

        System.out.println("冒泡排序运行时间：" + Time);
    }

    /**
     * 三、插入排序
     */
    @Test
    public void insertionSort(){

        System.out.println("原始数组为：");
        print(arr);
        System.out.println("\n");

        long startTime = System.currentTimeMillis();    //获取开始时间

        int n = 0; //定义交换次数
        int k = 1; //定义循环次数

        int d = 1; // 插入的间距为1
        for(int i = d ; i < arr.length; i++){

            System.out.print("经过第"+ "["+ k++ +"]" + "次循环之后，数组内容！");
            System.out.println("\n");
            System.out.println("===================================插入排序=======================================");

            for (int j = i; j > 0; j=j-d){   // j=j-d 将坐标向上一个间距的值移动一个间距单位
                if (arr[j] < arr[j-d]){      // j-d 是当前的值与上一个间距的值进行比较
                    swap(arr, j,j-d);
                n++;
                System.out.print("经过第"+ n + "次交换之后，数组内容！");
                print(arr);
                System.out.println("\n");
                }
            }
            System.out.println("***********************************插入排序***************************************");
        }

        long endTime = System.currentTimeMillis();    //获取结束时间

        long Time = endTime - startTime;

        System.out.println("插入排序运行时间：" + Time);
    }

    /**
     * 四、希尔排序
     */
    @Test
    public void shellSort(){

        System.out.println("原始数组为：");
        print(arr);
        System.out.println("\n");

        long startTime = System.currentTimeMillis();    //获取开始时间

        int n = 0; //定义交换次数
        int k = 1; //定义循环次数

        for (int d = arr.length / 2; d > 0; d = d/2){

            for(int i = d; i < arr.length; i++){

                System.out.print("经过第"+ "["+ k++ +"]" + "次循环之后，数组内容！");
                System.out.println("\n");
                System.out.println("===================================希尔排序=======================================");

                for (int j = i; j > d-1; j = j-d){
                    if (arr[j] < arr[j-d]){
                        swap(arr, j,j-d);
                        n++;
                        System.out.print("经过第"+ n + "次交换之后，数组内容！");
                        print(arr);
                        System.out.println("\n");
                    }
                }
                System.out.println("***********************************希尔排序***************************************");
            }
        }

        long endTime = System.currentTimeMillis();    //获取结束时间

        long Time = endTime - startTime;

        System.out.println("希尔排序运行时间：" + Time);
    }


    /**
     * 五、归并排序
     */

    @Test
    public void mergeSort(){

        long startTime = System.currentTimeMillis();    //获取开始时间

        System.out.println("原数组：");
        print(arr);
        System.out.println("\n");

        sort(arr,0,arr.length-1);

        long endTime = System.currentTimeMillis();    //获取结束时间

        long Time = endTime - startTime;

        System.out.println("归并排序运行时间：" + Time);
    }


    /**
     * 定义一个递归方法 调用合并方法
     * @param arr   数组
     * @param left
     * @param right
     */
    public void sort(Integer[] arr, int left, int right) {
        //当分到只剩下一个元素的情况,则退出递归程序
        if (left >= right)
            return;


        // 找出中间索引
        int mid = (left + right) / 2;

        sort(arr,left , mid);


        sort(arr, mid + 1, right);

        // 合并
        merge(arr, left, mid, right);


    }

    /**
     * 定义一个合并方法
     * @param arr
     * @param left
     * @param mid
     * @param right
     */
    public void merge(Integer[] arr, int left, int mid, int right) {
        //声明三个计时器
        int leftIndex = left;   //左边数组起止索引
        int rightIndex = mid + 1;  //右边数组起止索引
        int tempIndex = 0;    //临时数组起止索引

        //创建临时数组,长度为原组长度
        Integer[] tmp = new Integer[arr.length];

        //左边数组和右边数组都剩余时，比较当前两边索引位置，如果左边小于右边，将左边元素存入临时数组，反之将右边存入临时数组
        while (leftIndex <= mid && rightIndex <= right) {
            if (arr[leftIndex] <= arr[rightIndex]) {
                tmp[tempIndex ++] = arr[leftIndex ++];
            } else {
                tmp[tempIndex ++] = arr[rightIndex ++];
            }
        }
        //如果左边的还有剩余，右边为空时，将左边剩余的归并到临时数组
        while (leftIndex <= mid){
            tmp[tempIndex ++] = arr[leftIndex ++];
        }
        //如果右边的还有剩余，左边为空时，将右边剩余的归并到临时数组
        while (rightIndex <= right){
            tmp[tempIndex ++] = arr[rightIndex ++];
        }
        //将临时数组更新到原数组
        for(int t=0;t<tempIndex;t++){
			arr[left+t] = tmp[t];
		}

        System.out.println("===================================归并排序=======================================");
        System.out.print("开始合并temp数组排序：");
        print(tmp);
        System.out.println();

        System.out.print("arr改变:");
        print(arr);
        System.out.println();
        System.out.println("***********************************归并排序***************************************");
        System.out.println("\n");
    }


    /**
     * 六、快速排序
     */

    @Test
    public void quickSort(){

        long startTime = System.currentTimeMillis();    //获取开始时间

        System.out.print("原数组排序为：");
        print(arr);
        System.out.println("\n");

        quick(arr,0,arr.length-1);

        System.out.println();

        System.out.print("排序之后数组排序为：");
        print(arr);

        System.out.println("\n");
        long endTime = System.currentTimeMillis();    //获取结束时间

        long Time = endTime - startTime;

        System.out.println("插入排序运行时间：" + Time);
    }


    public void quick(Integer[] arr, Integer start, Integer end){
        if (start > end)
            return;

        int i = start;      //数组开始索引
        int j = end;        //数组结束索引
        int key = arr[i];   //基值

        System.out.println("===================================快速排序=======================================");

        while(i<j){
            while(i<j && arr[j] >= key){
                j--;

            }
            arr[i] = arr[j];

            while(i<j && arr[i] <= key){
                i++;

            }
            arr[j] = arr[i];
        }

        arr[i] = key;

        System.out.print("arr改变:");
        print(arr);
        System.out.println();
        System.out.println("***********************************快速排序***************************************");
        System.out.println();


        quick(arr,start,i-1);
        quick(arr,i+1,end);
    }


    /**
     * 定义一个打印方法
     * @param arr
     */
    public void print(Integer[] arr) {
        System.out.print("arr[]排序为:"+" ");
        for (int m = 0; m < arr.length; m++) {
            System.out.print(arr[m] + " ");
        }
    }


    /**
     * 定义一个交换方法
     */
    public void swap(Integer arr[],int i,int j){
        int temp = 0;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
